package a_doubleWrite;

/**
 * todo
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-07-27 09:59
 */
public class L134 {
    //输入:
    //gas  = [1,2,3,4,5]
    //cost = [3,4,5,1,2]
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            int j = i;//遍历gas作为起点
            int remain = gas[i];//剩余油
            while (remain >= cost[j]) {
                //gas[(j + 1) % n]下一个加油站
                remain = remain - cost[j] + gas[(j + 1) % n];
                j = (j + 1) % n;
                if (j == i) {//回到原地
                    return j;
                }
            }
            /*优化*/
            //情况1：，如果j到了i前面
            //* * * * * *
            //  ^   ^
            //  j   i
            if(j<i) return -1;
            //情况2：i最多到j,那么i-j之间节点无法循环
            //* * * * * *
            //^     ^
            //i     j
            i=j;
        }
        return -1;
    }
}
